package com.platform.modules.alg.alglib.poj2352;

public class Poj2352 {
    public String output = "";
    private int maxn = 32010;
    // 等级统计
    private int ans[] = new int[maxn];
    // 每个值的数量
    private int c[] = new int[maxn];
    int n;

    // c[i]的区间长度
    int lowbit(int x) {
        return (-x) & x;
    }

    // 将坐标为 x 的元素增加 val，其后继也要增加
    void add(int x, int val) {
        while (x <= maxn) {
            c[x] += val;
            x += lowbit(x);// x 的后继（父结点）
        }
    }

    // 前缀和
    int sum(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= lowbit(x); // x 的前驱
        }
        return s;
    }

    public String cal(String input) {
        String[] line = input.split("\n");

        n = Integer.parseInt(line[0]);
        int x, y;
        for (int i = 0; i < n; i++) {
            String[] num = line[i + 1].split(" ");
            x = Integer.parseInt(num[0]);
            y = Integer.parseInt(num[1]);
            x++;
            ans[sum(x)]++;
            add(x, 1); // x的数量 c[x] 增1
        }
        for (int i = 0; i < n; i++)
            output += ans[i] + "\n";

        return output;
    }
}
